/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 */
public class Test32 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()(())"));
    }
    public static int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int maxSize = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')'){
                if (s.charAt(i-1) == '('){
                    dp[i] = (i > 2 ? dp[i-2] : 0) + 2;
                }else if (s.charAt(i-1) == ')' && i-1-dp[i-1]>=0 && s.charAt(i-1-dp[i-1])=='('){
                    dp[i] = dp[i-1] + 2 + ( i-dp[i-1]-2>=0 ? dp[i-dp[i-1]-2] : 0);
                }
                maxSize = Math.max(maxSize,dp[i]);
            }
        }
        return maxSize;
    }
}
